# @Time    : 2020/11/18 3:43 下午
# @Author  : baii
# @File    : linked_list
# @Use     : python 模拟实现单链表


class Node(object):

    def __init__(self, e = None, next_node = None):
        # 该节点存储的数据
        self.e = e
        # 指向下一个节点
        self.next : Node = next_node


# 索引式链表
class LinkedList(object):

    def __init__(self):
        self.__dummy_head = Node()
        self.__size = 0

    def get_size(self):
        return self.__size

    def is_empty(self):
        return self.__size == 0

    def insert(self, index, e):
        if index < 0 or index > self.__size:
            raise Exception('Add failed. Require index >= 0 and index <= size.')

        prev = self.__dummy_head

        for i in range(index):
            prev = prev.next

        prev.next = Node(e, prev.next)

        self.__size += 1

    def add_first(self, e):
        # node = Node(e)
        # node.next = self.__head
        # self.__head = node
        self.insert(0, e)

    def add_last(self, e):
        self.insert(self.__size, e)

    def get(self, index):
        if index < 0 or index > self.__size - 1:
            raise Exception('Get failed. Require index >= 0 and index <= size.')

        cur = self.__dummy_head.next

        for i in range(index):
            cur = cur.next

        return cur.e

    def get_first(self):
        self.get(0)

    def get_last(self):
        self.get(self.__size)

    def set(self, index, e):
        if index < 0 or index > self.__size - 1:
            raise Exception('Set failed. Require index >= 0 and index <= size.')

        cur = self.__dummy_head.next

        for i in range(index):
            cur = cur.next

        cur.e = e

    def contains(self, e):

        cur = self.__dummy_head.next

        while cur != None:
            if cur.e == e:
                return True
            cur = cur.next

        return False

    def delete(self, index):
        if index < 0 or index > self.__size - 1:
            raise Exception('Delete failed. Require index >= 0 and index <= size.')

        prev = self.__dummy_head

        for i in range(index):
            prev = prev.next

        prev.next = prev.next.next

        self.__size -= 1

    def __str__(self):

        res = 'dummy_head'

        cur = self.__dummy_head.next

        while cur != None:
            res += ' => {}'.format(cur.e)
            cur = cur.next

        res += ' => None'

        return res


if __name__ == '__main__':
    linked_list = LinkedList()
    for i in range(10):
        linked_list.add_first(i)
    linked_list.insert(3, 666)
    print(linked_list)
    print(linked_list.get(10))

    print(linked_list.get_size())
    linked_list.delete(0)
    print(linked_list)

    print(None)